import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：两数相加
 * 思路：1. 将链表中的数全部储存起来，模拟计算的方法算出最终的结果，并创建链表存储起来
 *      2. 一边遍历链表一边就计算两个链表的节点值，并且创建链表，将计算出的节点值存储起来（优化思路）
 */
public class Test {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 遍历两个链表，模拟计算相加的方法来实现
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        int carry = 0;
        // 当有一方不为空时，我们就继续进行计算
        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            // 本位与上一位进位的结果相加
            int sum = val1 + val2 + carry;
            // 进位 是 逢10进1
            carry = sum / 10;

            cur.next = new ListNode(sum % 10);
            cur = cur.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 最后一位数相加完后还有进位的，那么就需要另外进位
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return head.next;
    }

    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        // 先把节点数全部算出来，再创建一个新的链表来存储其和
        if (l1.val == 0 && l2.val == 0) {
            return l1;
        }
        long sum1 = 0;
        for (int i = 0; l1 != null; i++) {
            sum1 += (long)Math.pow(10, i) * l1.val;
            l1 = l1.next;
        }
        long sum2 = 0;
        for (int i = 0; l2 != null; i++) {
            sum2 += (long)Math.pow(10, i) * l2.val;
            l2 = l2.next;
        }
        long sum = sum1 + sum2;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        for (; sum != 0; sum /= 10) {
            ListNode newNode = new ListNode((int)sum % 10);
            cur.next = newNode;
            cur = newNode;
        }
        return head.next;
    }

    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        // 用顺序表来接收其中的数据，再模拟计算的方法来进位，最后用队列来创建链表
        ArrayList<Integer> list1 = new ArrayList<>();
        while (l1 != null) {
            list1.add(l1.val);
            l1 = l1.next;
        }
        ArrayList<Integer> list2 = new ArrayList<>();
        while (l2 != null) {
            list2.add(l2.val);
            l2 = l2.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        int n = list1.size() - list2.size();
        ArrayList<Integer> listLong = list1;
        ArrayList<Integer> listShort = list2;
        if (n < 0) {
            // list1 的个数少于 list2
            n = -n;
            listLong = list2;
            listShort = list1;
        }
        int sizeLong = listLong.size();
        while (n-- > 0) {
            list.add(listLong.get(sizeLong-1));
            sizeLong--;
        }
        int sizeShort = listShort.size();
        // 开始相加元素
        while (sizeLong > 0) {
            int sum = listLong.get(sizeLong-1) + listShort.get(sizeShort-1);
            int i = 0;
            if (sum >= 10) {
                i++;
                sum /= 10;
            }
            if (list.size() != 0) {
                list.set(list.size()-1, (list.get(list.size()-1) + i));
            }
            list.add(sum);
            sizeLong--;
            sizeShort--;
        }
        // 开始创建链表
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        n = list.size();
        while (n-- > 0) {
            ListNode newNode = new ListNode(list.get(n));
            cur.next = newNode;
            cur = newNode;
        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(9);

        ListNode headB = new ListNode(9);
        //ListNode cur = addTwoNumbers(headA, headB);
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}